package Leetcode第二期;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : K k
 * @date : 9:57 2020/9/19
 * 计算给定二叉树的所有左叶子之和。
 *
 * 示例：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 */
public class 左叶子之和_404 {
    //思路：dfs 深度优先
    public int sumOfLeftLeaves(TreeNode root) {
       return  root==null? 0 :dfsSolver(root);
    }


    public int dfsSolver(TreeNode node){
       int sum=0;

       if(node.left!=null){
           sum+=isLeafNode(node.left)? node.left.val:dfsSolver(node.left);
       }
        if (node.right!=null && !isLeafNode(node.right)){
            sum+=dfsSolver(node.right);
        }
        return sum;
    }

    public boolean isLeafNode(TreeNode node){
        return node.left==null && node.right==null;
    }


    //迭代 广度优先
    public int sumOfLeftLeavesA(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                if (isLeafNode(node.left)) {
                    ans += node.left.val;
                } else {
                    queue.offer(node.left);
                }
            }
            if (node.right != null) {
                if (!isLeafNode(node.right)) {
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }
}
